package org.example.chap03;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/group-anagrams/
 */
public class GroupAnagrams {

    public static void main(String[] args) {
       String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> list = solution1(strs);
       for (List<String> mylist : list){

           for (String str:mylist){
               System.out.print(str+",");
           }
           System.out.println();
       }

//       List<String> arrayList = new ArrayList<>();
//        arrayList.add("1");
//
//        Map<String,List<String>> map = new HashMap<String,List<String>>();
//
//        map.put("k1",arrayList);
//        arrayList.add("2");
//        map.put("k1",arrayList);
//        System.out.println(map.toString());
    }

    /**
     * 由于互为字母异位词的两个字符串包含的字母相同，
     * 因此对两个字符串分别进行排序之后得到的字符串一定是相同的，
     * 故可以将排序之后的字符串作为哈希表的键
     * @return
     */
    public static List<List<String>> solution1(String[] strs){
       Map<String,List<String>> map = new HashMap<String,List<String>>();

        for (int i = 0; i < strs.length; i++) {
            String str = strs[i];
            //获取每个字符
            char[] charArray = str.toCharArray();
            //重排
            Arrays.sort(charArray);
            String sortStr = new String(charArray);
            List<String> list = map.getOrDefault(sortStr,new ArrayList<>());
            list.add(str);
            map.put(sortStr,list);
        }

        return new ArrayList<List<String>>(map.values());
    }
}
